1. Field of the Invention
Embodiments of the invention relate generally to a Post-Viterbi error correction method. More particularly, embodiments of the invention relate to a Post-Viterbi error correction method adapted to reduce a probability of mis-correction and an apparatus adapted to implement the method.
A claim of priority is made to Korean Patent Application No. 10-2006-0006818, filed on Jan. 23, 2006, the disclosure of which is incorporated by reference in its entirety.
2. Description of Related Art
Error detection and correction techniques play an important role in many data transmission systems where noise is present and accuracy matters. For example, in many electronic data transmission systems, error detection and correction is achieved by encoding data using some form of redundant data before transmitting the data across a channel and then using the redundant data to aid a process of decoding the data.
One common technique used for error correction is known as a cyclic redundancy check (CRC). In a cyclic redundancy check, data to be transmitted across a noisy channel is multiplied by a generator polynomial to form a codeword.
In this written description, the term “transmitted codeword” will denote an original codeword to be transmitted across a channel and the term “detected codeword” will denote the codeword as detected by a receiving device after the codeword has been transmitted across the channel. In addition, the generator polynomial can be referred to more generically as an error detection code, which can be designed from various types of polynomials.
A syndrome is computed from the detected codeword by dividing the detected codeword by the generator polynomial. A detected codeword without errors yields an all-zero syndrome, and a detected codeword containing errors yields a syndrome that is not all-zero.
A post-Viterbi processor is often used to find a most probable type of error pattern and a start position for the error pattern within a detected codeword by estimating an amount of correlation between known forms of error patterns and an estimated error signal.
The estimated error signal is typically computed as a difference between an output signal of an equalizer and a signal generated by convolution of an output of a Viterbi decoder with a partial response polynomial. The partial response polynomial is a signal that facilitates a digitalization of an analog readback channel by reshaping the analog readback channel into a known partial response using an equalizer. The Viterbi decoder computes the detected codeword from a reshaped, digitalized equalizer output.
Due to noise and an imperfect equalizer, the detected codeword may contain errors. Accordingly, the error signal is obtained by subtracting the equalizer output from the signal computed by convolving the Viterbi decoder output with the partial response polynomial.
As an example, FIG. 1 shows one type of Post-Viterbi processor. Referring FIG. 1, data is encoded by an error detection coding (EDC) encoder (not shown) and transmitted through a channel which may contain noise. An equalizer unit 106 reshapes a readback channel output into a sequence which is matched to a partial response P(D), where “D” is a delay variable in a digital sequence, e.g., P(D)=1+6D+7D2+2D3.
A partial response maximum likelihood (PRML) unit 108 detects a transmitted codeword and provides an output. An error signal ‘e’ is generated by subtracting an output of equalizer unit 106 and the output of PRML unit 108, convolved with partial response P(D).
An EDC decoder unit 112 computes a syndrome to check for the presence of errors in the detected codeword. A matched-filters unit 114 comprises a plurality of error pattern event matched filters, each corresponding to a dominant error pattern and used to detect whether the detected codeword contains one of the dominant error pattern. The term “dominant error pattern” here denotes an error pattern with a relatively high likelihood of occurrence among potential error patterns for a particular communication channel.
Each error-pattern matched filter calculates a likelihood value, or a confidence value, that an error pattern occurred in the detected codeword at a particular position. A select maximum unit 116 then selects an error pattern and associated start position having a maximum likelihood among the error patterns and start positions calculated by the error pattern matched filters. Then, based on the information about the most likely error pattern and start location, a correction unit 118 corrects the error pattern.
As an example of how the post-Viterbi processor works, assume that “a” is recorded data, “a prime” (a′) is recorded data decoded by PRML 108 and P(D) is a partial response polynomial. An output signal “y” of equalizer unit 106 and an error signal “e” can be expressed as y=a*p+n and e=(a−a′)*p+n, respectively, where “p” denotes a transfer function of a readback channel between the medium where the recorded data is stored and the output of the equalizer, “n” denotes noise in the readback channel, and * denotes a convolution operation.
A confidence value calculated by matched filters unit 114 can be expressed as an equation of P−1(D)*E−1(D), where, P−1(D) and E−1(D) denote time reversals of the partial response polynomial and an error pattern, respectively, and * denotes an convolution operation. Respective error pattern matched filters in matched filters unit 114 are used to calculate a probability of each error pattern, e.g., a confidence value, at every position within a detected codeword.
Select maximum unit 116 produces an error pattern and an error start position based on the largest confidence value among outputs of matched filters unit 114. Correction unit 118 then corrects a most likely error pattern according to the error pattern and error start position output from select maximum unit 116.
In channels with a relatively high incidence of errors (i.e., “interference-dominant” channels), errors tend to occur in specific patterns. For example, if a transmitted codeword is [1, −1, 1, −1, 1, 1, −1, 1, −1, −1], and a detected codeword is [1, −1, 1, −1, 1, −1, 1, −1, −1, −1], then an error pattern [0, 0, 0, 0, 0, 2, −2, 2, 0, 0] with a with a specific pattern denoted [2, −2, 2] has occurred.
FIG. 2 is a flow chart illustrating a conventional Post-Viterbi error correction method.
Referring to FIG. 2, an operation S202 is performed to determine whether or not an error pattern exists in a detected codeword. In operation S202, the detected codeword is divided by a generator polynomial to produce a syndrome. If the syndrome is all-zero, then the detected codeword presumably contains no errors. However, if the syndrome is not all-zero, the detected codeword presumably contains some error.
If the detected codeword is determined to be error free, a data recovery process is performed in an operation S206 to recover original data from which the detected codeword was formed. The data recovery process typically removes redundant bits that were added to the data by the EDC encoder to form a transmitted codeword.
On the other hand, if the detected codeword is determined to contain errors in operation S202, a Post-Viterbi error correction process is performed in an operation S204 to correct the errors.
Operation S204 is performed under a condition of K=1, where “K” denotes a maximum number of different error patterns which are assumed to possibly exist within the detected codeword. The relation of K≦E should be satisfied, where “E” denotes a number of error pattern matched filters included in the post-Viterbi processor.
In operation 204, confidence values are computed for all possible error patterns with respect to every bit of the detected codeword using respective error pattern matched filters corresponding to respective error patterns. Here, each error pattern matched filter is configured according to dominant error patterns occurring in the readback channel. Errors in the detected codeword are corrected according to the most likely error pattern that occurred and the most likely start position of the error pattern, as determined by the post-Viterbi processor.
Unfortunately, conventional Post-Viterbi error correction methods, such as that shown in FIG. 2, have a high possibility of mis-correction. A mis-correction occurs where either an incorrect error pattern is corrected, or an error pattern is corrected at the wrong start position.
For example, in perpendicular magnetic recoding (PMR), an error pattern ±[2,−2] is often detected as ±[2,−2,2] or ±[2,−2,0,2,−2]. Another dominant error pattern ±[2,−2,2] is often detected as ±[2,−2] or ±[2,−2,2,−2,2,−2]. Similarly, error pattern ±[2,−2,2,−2,2] and ±[2,−2,2,−2,2,−2] are also commonly mis-detected. On the other hand, with regard to mis-corrected start positions, dominant error patterns ±[2,−2] and ±[2,−2,2] are often corrected as ±[2,0,−2] or ±[2,0,0,−2].
FIG. 3 shows an example of mis-correction by the Post-Viterbi processor of FIG. 1. In this example, the Post-Viterbi processor performs error detection and correction based on the following six dominant error patterns [2,−2], [2,−2,2], [2,−2,2,−2], [2,−2,0,2,−2], [2,−2,2,−2,2], and [2,−2,2,−2,2,−2]. Referring to FIG. 3, an actual error pattern [2,−2, 2] has occurred with an actual error position [715, 716, 717], and K=1 in a detected codeword. However, an error pattern [2,−2,2,−2] with error position is [705,706,707,708] has a largest confidence value among the six dominant error patterns and therefore is determined to be a predicted error pattern by the Post-Viterbi processor.
Since the predicted error pattern is not the same as the actual error pattern, a mis-prediction has occurred, and as a result, the Post-Viterbi processor will perform a mis-correction. More particularly, error correction corresponding to the error pattern [2, −2, 2, −2] will be performed with respect to 705th through 708th bits of the detected codeword.
Unfortunately, mis-corrections such as these may have a significant impact on the bit error rate (BER) performance of the Post-Viterbi processor.